** *** *** ** ** ******** ******* ** **** **** ** * * ** ******** ******** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **** ******** ** ******* ******* ** ** ** ** ** ********* ** ** ** ** ** ** ******** ******** ********* ** ** ** ** ** ** ******** ******** Laboratorio di Analisi Algoritmi di Minimizzazione di Espressione Booleane by Giuliano Bossi Vincenzo Brescia Federica Molinari Versione 1.01 LAAMEB nella sua versione 1.01 e' distribuito secondo il criterio SHAREWARE, che permette agli utenti di provare un prodotto prima di decidere per un suo eventuale acquisto. L'unica differenza nelle versioni SHAREWARE e REGISTERED, consiste nell'impossibilita' dell'utente a salvare o caricare funzioni booleane in formato file. Inoltre, gli utenti registrati potranno avere una descrizione dettagliata degli algoritmi utilizzati e della loro implementazione. Viene peraltro incoraggiata la distribuzione di LAAMEB, purche' esso venga distribuito nella sua forma originale, e senza modifiche all'eseguibile e/o alla documentazione. Nessun compenso deve essere richiesto o corrisposto per la diffusione del pacchetto SHAREWARE di LAAMEB tranne per le spese sostenute per la sua duplicazione, e comunque per un costo non superiore alla quota di registrazione. Viene richiesto all'utilizzatore di registrare la sua licenza d'uso presso gli autori. La richiesta della licenza d'uso, che implica il pagamento di una quota di registrazione pari a lire 30000, permettera' al possessore di usufruire delle piene potenzialita' del programma per quanto riguardarda le routine di salvataggio e caricamento di file di funzioni booleane. La richiesta di licenza d'uso puo' essere effettuata tramite matrix al seguente indirizzo Fidonet: Giuliano Bossi 2:331/308.8@Fidonet.Org Oppure al seguente indirizzo Internet, via e-mail: Giuliano Bossi bossi@ghost.dsi.unimi.it Oppure mediante busta chiusa indirizzata a: Giuliano Bossi Via Fermi, 14 22050 Lomagna (CO) ITALIA Nella richiesta dovranno essere precisati : Il Cognome e Nome dell'utente, il suo eventuale indirizzo Fidonet a 4 dimensioni, ed un suo recapito telefonico. Gli autori non risponderanno ad eventuali messaggi riguardo all'utilizzo di LAAMEB, inviati da utenti che non abbiano provveduto a registrarsi. Eventuali bug possono essere segnalati a Giuliano Bossi attraverso una delle modalita' riportate sopra. Per quanto possibile gli autori cercheranno di porvi rimedio. Oltre a questo e a quanto riportato sopra non esistono limitazioni all'uso di LAAMEB legate alla non registrazione. Benche' il programma sia stato lungamente testato da un pool di Beta Tester gli autori non possono assumersi alcuna responsabilita' per danni dovuti all'utilizzo del programma. LAAMEB 1.01 pag. 3 INDICE: 0 Ringraziamenti.................................................pag. 4 1 Introduzione...................................................pag. 4 1.0 L'aritmetica booleana....................................pag. 4 1.1 Che cos'e' LAAMEB?.......................................pag. 6 1.2 L'algoritmo di minimizzazione di Quine-McCluskey.........pag. 6 1.3 Aspetti di implementazione dell'algoritmo................pag. 7 2 Come usare LAAMEB..............................................pag. 9 2.0 Le varie funzionalita' del programma.....................pag. 9 2.1 Il menu' File............................................pag. 9 2.1.0 Il comando Carica..................................pag. 9 2.1.1 Il comando Salva...................................pag. 10 2.1.2 Il comando Esci....................................pag. 10 2.2 Il menu' Funzione........................................pag. 11 2.2.0 Il comando Immetti.................................pag. 11 2.2.1 Il comando Calcola.................................pag. 11 2.2.2 Il comando Copertura...............................pag. 12 2.2.3 Il comando Statistica..............................pag. 12 2.2.4 Il comando Cancella................................pag. 12 2.3 Il menu' Algoritmo.......................................pag. 12 3 LAAMEB al lavoro...............................................pag. 13 3.0 Interpretazione dei risultati............................pag. 13 3.1 Alcuni esempi interessanti...............................pag. 14 4 Prospettive....................................................pag. 15 4.0 Come e' nato LAAMEB......................................pag. 16 4.1 Come potra' evolversi....................................pag. 16 5 Bibliografia...................................................pag. 16 LAAMEB 1.01 pag. 4 0 RINGRAZIAMENTI Gli autori desiderano ringraziare il prof. Mario Torelli del Dipartimento di Scienze dell'Informazione di Milano e Aaron Brancotti per gli utili consigli che hanno saputo dare a livello di implementazione del progetto. Un grosso grazie deve essere rivolto a Luca Ciastellardi, Pietro Toniolo, Andrea Biardi, Luigi Cristiano e tutto il clan di Euforia (2:331/308) per l'aiuto fornito nella chiusura del pacchetto e per la spietata revisione critica della documentazione. Inoltre, gli autori desiderano anche ringraziare Edina Patetta per la pazienza dimostrata e per il supporto morale. 1 INTRODUZIONE Questo capitolo vuole essere un'introduzione ragionata al mondo di LAAMEB, che e' il mondo della minimizzazione di espressioni booleane, con un occhio di riguardo agli algoritmi impiegati per risolvere questa classe di problemi. Il paragrafo 1.0 contiene un breve cappello sull'algebra e l'aritmetica di Boole e puo' quindi essere saltato da chi e' in possesso di queste conoscenze. 1.0 L'ARITMETICA BOOLEANA Dato che LAAMEB si occupa di funzioni booleane e' necessario fornire un minimo di background riguardo a questo argomento. Una funzione o espressione booleana puo' essere caratterizzata in molti modi. Uno dei piu' classici e' l'uso di una tabella di verita' del tipo a b | a or b -------+-------- 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1 Il linguaggio delle espressioni booleane e' quello dell'algebra di Boole, che si basa su un dominio caratterizzato da due diversi valori, 0 o falso e 1 o vero, composti opportunamente mediante le funzioni AND, OR, NOT con le seguenti tabelle di verita' (quella dell'OR e' stata data precedentemente): a b | a and b a | not a -------+--------- ----+------- 0 0 | 0 0 | 1 0 1 | 0 1 | 0 1 0 | 0 1 1 | 1 Queste sole semplici operazioni vengono usate per costruire funzioni anche molto complesse. A seconda del contesto si possono interpretare le funzioni and, or e not come moltiplicazione, addizione e opposto dell'aritmetica booleana piuttosto che come intersezione, unione e complementare insiemistico. Ricordiamo inoltre che, per quanto concerne le priorita', il not e' l'operazione a priorita' piu' elevata, seguito da and e or nell'ordine. Se intese nel senso dell'aritmetica booleana le operazioni suddette godono delle normali proprieta' dell'aritmetica dei numeri, come la commutativita', l'associativita', ecc. A noi interessa piu' da vicino il discorso dell'aritmetica booleana e quindi fissiamo, da un punto di vista notazionale, le seguenti convenzioni: - A meno che non vi sia una necessita' specifica esprimeremo and, or e not in termini di aritmetica booleana e quindi a and b --> a * b LAAMEB 1.01 pag. 5 a or b --> a + b not a --> A - In merito proprio all'uso del not e' da intendersi che useremo le lettere minuscole per le variabili semplici e quelle maiuscole per quelle negate. - A meno che non vi sia una necessita' specifica ometteremo l'uso di * per indicare l'and e concateneremo semplicemente le variabili coinvolte nell'espressione. Cosi' facendo otterremo cose come a * b * c --> abc - In virtu' di quest'ultima convenzione useremo solo ed esclusivamente variabili il cui nome sia identificato da un'unica lettera. Esempio: seguendo questa serie di convenzioni il normale or esclusivo (funzione che vale 1 quando i suoi argomenti sono diversi) potrebbe essere espresso come XOR(a, b) = Ab + aB Quando una funzione booleana e' espressa in questa forma si dice che e' in forma SP, ovvero somma di prodotti, in quanto e' caratterizzata da una somma di una serie di termini, espressi come prodotti di variabili semplici o negate. Un termine e' definito proprio come uno qualsiasi di questi prodotti. Da quanto detto e' evidente che si potrebbero immaginare funzioni in molte variabili e a valori in domini di cardinalita' n-esima, con n generico. Nel nostro caso pero' ci occuperemo solo di funzioni che hanno un unico valore, e che possono quindi essere espresse completamente mediante un'unica tabella di verita'. Noi utilizzeremo due diverse forme per specificare la funzione da minimizzare e quella minimizzata. Nel primo caso identificheremo la funzione in ingresso in modo univoco mediante l'elenco dei mintermini che la compongono e del numero di variabili che ne fanno parte, mentre nel secondo useremo la forma SP. Un mintermine e' un 1 della funzione, ovvero una configurazione binaria delle variabili in ingresso per cui la funzione vale 1. Questa configurazione viene interpretata come numero in base 2 e il mintermine viene solitamente espresso nel suo corrispettivo in base 10. Esempio: vediamo come si esprime in mintermini la seguente funzione f(a, b, c, d) a 4 variabili, identificata da questa tabella di verita' a b c d | f -------------+---- 0 0 0 0 | 1 --> mintermine 0 0 0 0 1 | 1 --> " 1 0 0 1 0 | 1 --> " 2 0 0 1 1 | 0 0 1 0 0 | 0 0 1 0 1 | 0 0 1 1 0 | 1 --> " 6 0 1 1 1 | 1 --> " 7 1 0 0 0 | 1 --> " 8 1 0 0 1 | 0 1 0 1 0 | 1 --> " 10 1 0 1 1 | 0 1 1 0 0 | 1 --> " 12 1 1 0 1 | 0 1 1 1 0 | 1 --> " 14 1 1 1 1 | 1 --> " 15 La funzione f puo' quindi essere espressa come ä4(0,1,2,6,7,8,10,12,14,15) LAAMEB 1.01 pag. 6 dove 4 e' il numero delle variabili che la compongono (in genere si parte da a in ordine alfabetico e quindi a, b, c, d), ä esprime la forma SP e i numeri 0, 1, 2, 6, 7, 8, 10, 12, 14, 15 fra parentesi esprimono l'elenco dei mintermini che la costituiscono. Questo tipo di notazione deriva direttamente dalle mappe di Karnaugh, forma tabellare di rappresentazione delle funzioni booleane utilizzate proprio per la minimizzazione manuale di semplici funzioni (fino a 5 variabili). Gli ultimi concetti che devono essere appresi per poter parlare di minimizzazione sono quelli legati agli implicanti di una funzione, gli implicanti primi, le tabelle cicliche e le forme irriducibili, da cui discendono le forme minime, obiettivo dell'elaborazione di LAAMEB, ma saranno trattati tutti in modo esauriente piu' avanti. 1.1 CHE COS'E' LAAMEB? LAAMEB, acronimo che sta per Laboratorio di Analisi Algoritmi di Minimizzazione di Espressioni Booleane, e' un programma per la valutazione di algoritmi, tempi di esecuzione e bonta' delle soluzioni, nell'ambito della minimizzazione di espressioni booleane. L'algoritmo base implementato ed analizzato Š quello di Quine-McCluskey, descritto nel Luccio, la cui esecuzione si divide in 2 fasi, A e B, descritte ed analizzate pi— dettagliatamente nel prosieguo. LAAMEB puo' essere pensato quindi come un sistema tramite il quale e' possibile inserire delle funzioni booleane, minimizzarle e valutare la validita' della minimizzazione mediante la redirezione di statistiche opportune. 1.2 L'ALGORITMO DI MINIMIZZAZIONE DI QUINE-MCCLUSKEY Come gia' accennato LAAMEB si basa su di un particolare algoritmo di minimizzazione, quello detto di Quine-McCluskey. Questo algoritmo deriva dall'applicazione del ben noto teorema dell'algebra di Boole detto di De Morgan e corrisponde all'utilizzo delle mappe di Karnaugh nella minimizzazione manuale. L'algoritmo e' diviso in due fasi, dette banalmente fase A e fase B. Nella prima fase, partendo dall'elenco dei mintermini forniti, viene generato, attraverso iterazioni successive, l'elenco degli implicanti primi. Un implicante e' una configurazione particolare di variabili all'ingresso il cui valore di verita' (1), implica la verita' anche della funzione intera. Ad esempio nel caso della funzione data prima, il mintermine 6, identificato anche da AbcD, e' un implicante della funzione. Infatti, quando AbcD = 1 si verifica necessariamente che anche f = 1, in quanto affinche' AbcD sia 1 deve essere per forza a = 0, b = 1, c = 1 e d = 0 e percio' f(a, b, c, d) = 1. I mintermini sono gli implicanti base, quelli di partenza. Applicando successivamente un certo tipo di calcolo si vengono a fondere certi implicanti l'uno con l'altro, con l'obiettivo di arrivare all'insieme di implicanti primi della funzione. Questi implicanti vengono detti primi, in quanto caratterizzati dal fatto che non sono implicati da nessun altro implicante. Nell'esempio di prima il mintermine AbcD non puo' essere un implicante primo, perche' e' implicato dall'implicante Abc, che a sua volta non e' primo in quanto implicato dall'implicante bc, che invece e' primo. E' abbastanza facile verificare la veridicita' di queste affermazioni. Questo e' comunque cio' che avviene durante la fase A, che e' quella meno pesante da un punto di vista del calcolo. Durante la fase B, invece, vengono costruite delle tabelle dove sulle righe si indicizzano gli implicanti primi ottenuti dalla fase A, mentre sulle colonne si indicizzano i mintermini. In questa fase si cerca innanzitutto di costruire un insieme di implicanti primi che copra tutti i mintermini (non bisogna cioe' "dimenticare" nessun 1 della funzione, altrimenti otterremo una funzione diversa) e che sia privo di implicanti primi superflui. Un insieme siffatto viene detto forma irridondante della funzione e corrisponde all'eliminazione dalla scrittura della funzione di tutti gli implicanti LAAMEB 1.01 pag. 7 primi che non sono necessari in qualche forma SP. Ad esempio nella solita funzione di prima l'elenco degli implicanti primi e': ABC, BD, cD, aD, bc Questi implicanti non concorrono tutti a formare la soluzione minima. Se si pigliassero in toto si avrebbe l'espressione: ABC + BD + cD + aD + bc che ha la stessa tabella di verita' di f, ma non e' l'espressione minima. Infatti, come si puo' facilmente constatare, l'espressione: ABC + cD + aD + bc corrisponde ugualmente alla funzione f, ma e' costituita da un numero minimo di implicanti. L'esecuzione dell'algoritmo di Quine-McCluskey garantisce che l'insieme trovato al termine dell'esecuzione sia irridondante e minimo. E' bene precisare una cosa a questo punto: una forma irridondante non e' necessariamente minima, mentre e' vero il contrario. La ricerca della forma minima di un'espressione booleana avviene quindi nello spazio delle forme irridondanti dell'espressione. In realta' poi, la ricerca si estende anche a forme ridondanti: cio' e' dovuto al modo in cui gli algoritmi forzano la riduzione di una tabella ciclica (vedi sotto). Si rimanda alla letteratura specialistica per un approfondimento riguardo a questo argomento. Se l'algoritmo viene interrotto e non puo' terminare l'esecuzione, l'unica garanzia data e' la copertura della funzione da parte della soluzione parziale. Nel corso dell'esecuzione della fase B, come detto, l'elemento sul quale si lavora e' una tabella, detta ciclica. Senza entrare nel merito del significato della ciclicita' di tali tabelle, va detto che la minimizzazione di siffatte tabelle viene effettuata mediante criteri non deterministici esaustivi, che vanno cioe' a considerare tutte le possibili ramificazioni dovute ad una scelta non deterministica. Dopo aver effettuato una di queste scelte e' facile che se ne debbano compiere altre sulla strada che si e' presa: questo genera ulteriori ramificazioni, che a loro volta possono ramificarsi ancora e cosi' via. Algoritmi di questo tipo, che presentano cioe' una fase di "branching", presentano tempi di complessita' di tipo esponenziale, e vengono risolti con implementazioni di tipo ricorsivo. Nel nostro caso il tempo di esecuzione e' dell'ordine di 2^(2^I) nel caso peggiore, dove I e' il numero di mintermini della funzione. L'albero delle scelte che viene generato e' un albero binario, che puo' facilmente raggiungere una profondita' di 25, 26 livelli anche per funzioni a 6 variabili. Negli esempi presenti in questa documentazione viene descritta l'esecuzione della minimizzazione di una funzione di 6 variabili, che ha richiesto l'analisi e la riduzione di piu' di 3 milioni di tabelle cicliche. 1.3 ASPETTI DI IMPLEMENTAZIONE DEL PROGETTO L'aspetto sicuramente piu' interessante tra quelli analizzati in fase di implementazione del progetto, e' stato la creazione di un meccanismo di attraversamento dell'albero delle scelte semplice ed efficiente, che permettesse in modo agevole l'interruzione e la ripresa dell'esecuzione. Si doveva cioe' implementare un algoritmo di attraversamento di tipo preorder molto duttile e maneggevole. Ci si e' orientati allora verso un algoritmo iterativo che assolvesse tutte le funzionalita' di tipo ricorsivo della natura del problema, seguendo la stessa tecnica che utilizzano certi compilatori per sciogliere una ricorsione: l'"end-recursion removal", descritta dal Sedgewick nel V capitolo. Questa tecnica fruisce di uno stack, nel quale memorizza i nodi che devono ancora essere attraversati. La dimensione di questo stack, ovvero il numero di nodi in esso contenuti, da' un'idea, a run-time, della profondita' dell'albero delle tabelle cicliche per la funzione in minimizzazione. Se si trattasse di un albero completo bisognerebbe tenere presente che, se N fosse la sua profondita', 2^N sarebbe il numero di nodi di cui esso e' composto, da cui la complessita' astronomica di funzioni a prima vista innocue, fenomeno denominato esplosione combinatoria. Questo algoritmo di attraversamento e' stato implementato in 3 versioni LAAMEB 1.01 pag. 8 differenti, denominate Quine I, Quine II, e Fast Quine (per capire quanto segue e' necessario aver bene presente come viene simboleggiato un albero binario e che tipo di operazioni si fanno su di esso; si consiglia di consultare i primi capitoli del Sedgewick per avere informazioni piu' approfondite). - QUINE I: e' l'algoritmo di Quine-McCluskey, come descritto nel Luccio. Vengono esaminate tutte le scelte possibili e non viene effettuato nessun taglio "intelligente" su queste. - QUINE II: e' la versione modificata dell'algoritmo di Quine-McCluskey, nella quale un nodo viene esaminato o inserito nello stack solo se questa scelta puo' essere conveniente, ovvero se il numero di implicanti primi che compongono la forma irridondante del nodo e' minore del numero di implicanti primi della soluzione corrente. Infatti, durante le riduzioni successive gli implicanti primi che compongono la forma irridondante possono solo aumentare; va da se' quindi che non si ha nessuna convenienza a prendere in esame nodi svantaggiosi ancora prima della riduzione. - FAST QUINE: a differenza delle prime 2 versioni questa non assicura il raggiungimento della forma minima, in quanto non esamina tutto l'albero, bensŤ solo proseguendo lungo direzioni precise. Ogni algoritmo, e non solo l'ultimo, presenta due diverse direzioni di attraversamento, destra o sinistra. Ognuna delle due direzioni corrisponde ad un tipo preciso di scelta non deterministica. In pratica si utilizza sempre la regola di dominanza verso destra e di essenzialita' verso sinistra. Per chi fosse interessato ai concetti di dominanza ed essenzialita' si rimanda alla letteratura specializzata (Luccio). In generale per quanto riguarda i primi due algoritmi andare a destra significa solo che dal padre si andra' a visitare prima il nodo di destra, e poi quello di sinistra, compiendo un attraversamento in preordine "inverso", del tipo visita-vai_a_destra-vai_a_sinistra; andare a sinistra significa invece andare prima a sinistra e poi a destra dopo aver visitato il nodo, compiendo cosi' un classico preorder. Discorso a parte merita l'ultimo algoritmo, FAST QUINE, che non vede un albero ma a partire da un certo nodo, guardando sempre e solo nella direzione specificata, si comporta come se stesse scorrendo una lista, i cui nodi sono contenuti nello stack. In questo modo FAST QUINE esamina solo la dorsale di sinistra o quella di destra dell'albero (applicando solo l'essenzialita' o solo la dominanza), e porta nel primo caso alla foglia all'estremit… sinistra e nel secondo alla foglia all'estremit… destra. Entrando piu' nei particolari, l'elemento fondamentale della fase B, qualunque sia l'algoritmo utilizzato, e' il ciclo di estrazione, riduzione e immissione dei nodi nello stack. Le procedure che svolgono questo compito sono state scritte nel modo piu' semplice ed efficace possibile, con particolare riguardo a quelle di analisi e aggiornamento di una tabella, in quanto compongono cio' che viene definito "the inner loop", il ciclo piu' interno della fase B. Con questa espressione si intende quel nucleo di istruzioni che si trova al livello piu' interno di nidificazione dei cicli, e che quindi viene eseguito pi— frequentemente. E' stato adottato un meccanismo particolare di implementazione delle tabelle, viste come dei vettori sui quali le celle sono indirizzate con un criterio di spiazzamento. Questo permette innanzitutto una gestione rapida e semplice, ed un'allocazione dinamica che permette di mantenere diverse funzioni in memoria contemporaneamente. LAAMEB 1.01 pag. 9 2 COME USARE LAAMEB In questo capitolo viene descritto dettagliatamente il programma nelle sue funzionalita', e costituisce quindi, a tutti gli effetti, un manuale d'uso. 2.0 LE VARIE FUNZIONALITA' DEL PROGRAMMA Il programma presenta un unico parametro sulla linea di comando: LAAMEB [PR_CYCLE] Per PR_CYCLE si intende il numero di forme che devono essere paragonate affinche' venga effettuato il refresh dei dati a video nel corso della fase B. Nel caso di funzioni molto complesse, e' meglio dimensionare questo parametro in misura molto elevata, nell'ordine delle migliaia di tabelle, per evitare che la maggior parte del tempo di cpu sia speso per fare stampe a video della situazione attuale. Ad ogni modo e' sempre possibile interrompere l'esecuzione in un momento qualsiasi della fase B, andando a visualizzare le statistiche dettagliate, per poi riprendere da dove si era interrotto. Il parametro PR_CYCLE deve essere specificato e puo' avere valore compreso tra 0 e 65535; il valore 0 indica che non deve essere effettuato alcun refresh sino a quando il calcolo di minimizzazione non e' terminato. Al di la' di questo parametro iniziale il programma presenta un ambiente composto da un'ampia area di informazione e menu' a tendina per l'interazione con l'utente. La prima schermata, in particolare, da' informazioni sull'avvenuta registrazione del programma e sugli autori. Passata questa schermata l'utente puo' fondamentalmente compiere 3 diversi tipi di azione, ognuna legata ad un menu' (che e' a sua volta descritto in un paragrafo particolare e relativi sottoparagrafi): - File: si intendono operazioni di caricamento e/o salvataggio di file di funzioni, nonche' l'uscita dal programma; - Funzione: si intende l'immissione, o il calcolo o la visualizzazione di una funzione, nonche' alcune altre operazioni ad essa collegate; - Algoritmo: mediante questo menu' si effettua la scelta dell'algoritmo di minimizzazione. Le varie voci dei menu' sono richiamabili spostandosi con i tasti cursore ed utilizzando il tasto INVIO (o RETURN) per l'attivazione, una volta raggiunta la posizione desiderata. Escludendo le fasi di calcolo e redazione delle statistiche, nella meta' inferiore dello schermo e' sempre presente una descrizione sommaria delle 10 funzioni caricate, in forma: äv(n1,n2,n3,n4,n5,n6,n7,...) dove v e' il numero di variabili della funzione, ni e' l'i-esimo mintermine, e gli eventuali puntini di interpunzione segnalano la mancanza di spazio per la visualizzazione dell'intero elenco di mintermini. Ogni funzione viene identificata con il numero assegnatole in questa parte dello schermo, dall'immissione fino alla rimozione per salvataggio binario o cancellazione. 2.1 IL MENU' FILE Permette di eseguire tutte le operazioni di amministrazione dei file, nonche' l'uscita dal programma. Le opzioni possibili sono 3: - caricamento di un file contenente una o piu' funzioni precedentemente salvate in formato binario; - salvataggio di una o piu' funzioni in formato binario o di una sola in formato testo; - uscita dal programma. 2.1.0 Il comando Carica Carica da file binario funzioni precedentemente salvate. I dati da fornire nella maschera di input sono: - nome del file, path compreso (max 99 caratteri). Viene quindi richiesta conferma se i dati inseriti sono corretti. Il LAAMEB 1.01 pag. 10 programma tenta di caricare tutte le funzioni contenute nel file specificato, funzioni che devono essere state salvate precedentemente in formato binario, e segnala all'utente eventuali problemi di memoria o di spazio per le funzioni (se ne possono avere al massimo 10 contemporaneamente in memoria). Questa funzione non e' disponibile nella versione SHAREWARE. 2.1.1 Il comando Salva Salva funzioni su file. Scegliendo tale opzione viene poi richiesto il tipo di file su cui si intende salvare la funzione: - file di tipo testo: la consultazione del file puo' avvenire solo fuori dall'esecuzione del progetto LAAMEB utilizzando un editor qualsiasi. Il formato del file testo Š il seguente: RISULTATI GENERALI * Elenco mintermini * Numero di variabili * Stato elaborazione * Generazione input * Tempo totale di elaborazione RISULTATI FASE A * Tempo elaborazione * Numero implicanti primi * Elenco implicanti primi RISULTATI FASE B * Tempo elaborazione * Numero forme prime paragonate * Numero tabelle cicliche esaminate * Numero tabelle presenti nello stack * Numero implicanti soluzione * Soluzione Quest'ultimo campo cambia in base al tipo di soluzione pervenuta, che dipende direttamente dal tipo di elaborazione. Le scritte possibili sono: SOLUZIONE (forma minima) SOLUZIONE migliore determinata tra le forme esaminate SOLUZIONE migliore corrente (relativo al caso in cui lo stato e' sospeso) Nel caso in cui la soluzione risulti 1 costante l'unico implicante primo ottenuto e' della forma "- - - - -", cioe' tanti trattini quante sono le variabili; tale formato viene visualizzato nell'elenco degli implicanti primi in Fase A e viene scritta la definizione "1 COSTANTE" nel campo Soluzione della Fase B. Tra questi dati non compare l'algoritmo utilizzato nel corso della minimizzazione. Questa scelta non deve stupire, in quanto l'utente, interrompendo l'esecuzione del calcolo, puo' anche scegliere di cambiare l'algoritmo utilizzato. In questo modo non avrebbe molto senso anche solo riportare l'ultimo adottato. - file di tipo binario: tutte le informazioni riguardante una o piu' funzioni vengono salvate in un formato opportuno non editabile, per poter consentire agevolmente la ripresa in un secondo tempo. In questo caso poi le funzioni vengono cancellate dalla memoria. In entrambi i casi i dati da fornire sono: - le funzioni, mediante riferimento numerico - nome del file, path compreso (max 99 caratteri) Viene quindi richiesta conferma se i dati inseriti sono corretti. Questa funzione non e' disponibile nella versione SHAREWARE. 2.1.2 Esci Esce dal programma, chiedendo conferma dell'uscita. Inoltre per ogni funzione presente in memoria chiede all'utente se desidera LAAMEB 1.01 pag. 11 che queste vengano salvate, con un progressivo automatico del tipo "f#.laa", dove con # si intende il riferimento numerico alla funzione. 2.2 IL MENU' FUNZIONE Permette di eseguire tutte le operazioni inerenti ad una funzione. Le opzioni possibili sono 5: - immissione di una funzione in uno dei tre modi ammessi, mediante elencazione dei mintermini, generazione casuale dei mintermini o elencazione delle configurazioni; - calcolo della minimizzazione di una funzione attraverso l'algoritmo e la direzione specificati; - verifica della copertura di una funzione da parte della soluzione attualmente disponibile; - generazione delle statistiche di elaborazione di una funzione, aggiornate allo stato attuale del calcolo; - cancellazione di una funzione attualmente in memoria. 2.2.0 Il comando Immetti Immette una funzione attraverso uno dei tre modi possibili. Una volta scelto il comando di immissione vi sono tre modi ammessi per specificare il tipo di immissione, ad ognuno dei quali corrisponde un sottocomando. In ognuno dei tre casi e' necessario specificare, come prima cosa, il numero delle variabili della nuova funzione, in numero compreso tra 1 e 26. - Elenco: la forma piu' naturale per immettere una funzione e' l'elencazione dei suoi mintermini. Questi vengono inseriti nell'ordine desiderato in una stringa lunga al massimo 99 caratteri della forma n1, n2, n3-n4, n5, n6-n7, ... dove gruppi di mintermini vengono separati dalla virgola, ed ogni gruppo puo' essere un mintermine semplice (ad es. 13), oppure un range di mintermini (ad es. 23-78, cui corrispondono tutti i mintermini da 23 a 78 estremi compresi). In questo modo, la funzione precedentemente discussa puo' essere immessa come 0-2, 6-8, 10, 12, 14, 15 - Casuale: in questo caso si richiede al programma di generare in modo pseudo-casuale l'elenco dei mintermini. Questi vengono generati a partire da un seme specificato dall'utente, che permettera' quindi in seguito la stessa rigenerazione a partire dallo stesso seme. Viene richiesto quindi all'utente il numero di mintermini che si desiderano, e il seme, che deve essere un numero compreso tra 0 e 65535. Lavorando con 4 variabili, richiedere 10 mintermini generati a partire dal seme 37 vuol dire richiedere i mintermini 13, 14, 1, 11, 9, 15, 6, 7, 0, 8 - Configurazioni: ad ogni mintermine, in quanto configurazione di bit 1 o 0, puo' essere associato il numero di 1 di cui e' composto. Il mintermine 13, per esempio, corrisponde a 1101, ed e' quindi composto da 3 bit dal valore 1. Lavorando con 4 variabili, richiedere tutte le configurazioni di mintermini composte da 1 a 3 bit di valore 1 significa richiedere tutti i mintermini 8, 4, 2, 1, 12, 10, 9, 6, 5, 3, 14, 13, 11, 7 2.2.1 Il comando Calcola Calcola una funzione. Tramite questo comando viene avviato il calcolo della minimizzazione della funzione specificata, individuata mediante riferimento numerico. Il calcolo, come gia' detto, viene diviso in due fasi: fase A, di calcolo degli implicanti primi, e fase B, di calcolo della forma minima fra quelle irridondanti. La prima schermata visualizzata e' quella corrispondente alla fase A, e non e' interrompibile. Terminata questa fase si puo' abbandonare l'elaborazione o iniziare la fase B, notoriamente piu' lunga per le funzioni LAAMEB 1.01 pag. 12 computazionalmente piu' pesanti. Per questo motivo la fase B puo' essere interrotta in un punto qualsiasi, per poi essere ripresa nel momento desiderato. Nel corso di entrambe le fasi vengono visualizzate delle informazioni, che fotografano lo stato attuale della minimizzazione, come il numero di implicanti primi, la soluzione parziale, il numero di tabelle ridotte, ecc. Nel corso della fase A, composta al massimo da 2^V iterazioni (dove V e' il numero delle variabili della funzione), queste informazioni vengono visualizzate ad ogni iterazione. Durante la fase B, invece, la frequenza di aggiornamento delle informazioni a schermo e' regolata, come detto, dal parametro PR_CYCLE della linea di comando di LAAMEB. La frequenza massima che si puo' avere coincide con il valore 1 di PR_CYCLE: in questo caso ogni volta che viene ridotta una tabella ciclica si aggiornano le informazioni a schermo. Si consiglia di mantenere elevato questo parametro per le funzioni piu' complesse, nell'ordine delle migliaia o decine di migliaia di tabelle cicliche. 2.2.2 Il comando Copertura Verifica la copertura di una funzione. Una funzione in forma SP si puo' dire coperta nel momento in cui i prodotti di cui la somma e' composta implicano tutti e soli i mintermini della funzione. In pratica, in questo modo si verifica se la forma SP, che rappresenta la soluzione corrente, e' veramente equivalente alla funzione nella forma iniziale, cioe' espressa mediante i suoi mintermini. Questo comando ha una funzione di controllo sull'esattezza del risultato, ed e' stato inserito in origine piu' per effettuare comodamente il debugging che altro, visto che l'algoritmo di Quine-McCluskey, una volta implementato correttamente, garantisce di per se' l'equivalenza delle due forme della funzione. Oggi la sua presenza ha solo un valore di controllo formale e per questo motivo gli autori hanno preferito lasciarlo. Cosi' come per il comando precedente, la funzione che si vuole verificare deve essere specificata tramite riferimento numerico. 2.2.3 Il comando Statistica Visualizza le statistiche del calcolo di una funzione. Mediante questo comando vengono visualizzate a schermo le informazioni inerenti alla minimizzazione di una funzione. Queste informazioni sono le stesse che vengono stampate su file di testo mediante il comando Salva, anche se sono visualizzate con un layout un poco diverso. La funzione, di cui si desiderano le statistiche, deve essere naturalmente individuata mediante riferimento numerico. 2.2.4 Il comando Cancella Cancella una funzione. All'interno di LAAMEB possono essere presenti contemporaneamente al massimo 10 funzioni. Questo numero puo' ulteriormente scendere se si tratta di funzioni dall'elaborazione non terminata e composte da grandi tabelle. Per far posto a nuove funzioni e' dunque necessario eliminare qualcuna di quelle vecchie. Come gia' detto il comando Salva su file binario elimina automaticamente dalla memoria la funzione salvata. Se non si vogliono salvare le informazioni su file e' possibile semplicemente cancellare una funzione dalla memoria tramite il comando Cancella, specificandola attraverso il solito riferimento numerico. Attenzione: una volta cancellata una funzione e' definitivamente persa, e deve essere manualmente reimmessa nel caso in cui si desideri nuovamente la soluzione. 2.3 IL MENU' ALGORITMO Con il menu' algoritmo l'utente puo' scegliere il tipo di algoritmo da utilizzare per la prossima elaborazione. Gli algoritmi a disposizione sono, come detto, tre: Quine I, Quine II e Fast Quine (per una descrizione sommaria degli stessi si rimanda al capitolo 1.3). Di ogni algoritmo si hanno a disposizione due diverse direzioni di lavoro, Sinistra e Destra. LAAMEB 1.01 pag. 13 E' possibile attivare l'algoritmo voluto spostando la barra evidenziatrice e digitando INVIO in corrispondenza della scelta desiderata. In alto a destra, sulla barra dei menu', e sempre disponibile una scritta che individua l'algoritmo che si sta utilizzando, ad es. Quine II dx. 3 LAAMEB AL LAVORO LAAMEB e' fondamentalmente un programma di calcolo orientato alla presentazione e all'analisi delle statistiche del calcolo, percio' il modo migliore per presentare LAAMEB e' quello di vederlo sul campo di battaglia. Il problema della minimizzazione e' un problema non banale: appartiene alla classe dei problemi NP completi, cioe' la cui complessita' di calcolo e' di tipo non polinomiale. Come gia' accennato in precedenza, questa complessita' e' dovuta alla necessita' di percorrere tutto un albero, che puo' raggiungere con notevole facilita' un numero considerevole di livelli. Anche se pieni di buchi, si ha tranquillamente a che fare con alberi composti da migliaia di nodi, e in certi casi addirittura milioni. 3.0 INTERPRETAZIONE DEI RISULTATI Utilizzando LAAMEB con funzioni molto diverse tra loro si giunge ad alcuni risultati interessanti. Come detto, la fase A e' quella computazionalmente meno preoccupante, anche se si tratta dopotutto di un algoritmo di tipo esponenziale, con ordine di complessita' di 2^I, I numero dei mintermini della funzione. I tempi di fase A piu' lunghi sono quelli relativi a funzioni quasi "piene": con questa espressione si intendono funzioni con un elevato numero di mintermini, al limite tutti i mintermini possibili, che sono 2^V (V numero delle variabili della funzione). La funzione che ha tutti i mintermini possibili presenta un tempo di fase A rilevante (dipendente comunque anche da V, in quanto il numero di iterazioni della fase A e' al massimo proprio V) e un tempo di fase B nullo, perche' al termine della fase A si puo' immediatamente constatare che si tratta della funzione 1 costante. Nei casi in cui si osservano tempi lunghi di fase A, si hanno solitamente soluzioni abbastanza brevi in fase B, il cui ordine di complessita' e' comunque esponenziale del precedente, cioe' 2^(2^I). L'elevato tempo di fase A corrisponde quasi sempre alla produzione di un numero di implicanti primi molto basso, al limite nessuno nel caso di 1 costante. Nel momento in cui vi siano pochi implicanti primi e' praticamente impossibile che si creino tabelle cicliche, e quindi la fase B termina in un solo passo di riduzione. La fase B e' quella che merita maggiore attenzione. Dopo un certo numero di prove si e' osservato che il tempo di elaborazione dipende naturalmente dal numero di tabelle cicliche ridotte. Questo numero e' direttamente collegato al numero e alla forma degli implicanti primi prodotti in fase A, cioe' il numero di tabelle cicliche da ridurre aumenta con l'aumentare degli implicanti primi e soprattutto aumenta mostruosamente nel momento in cui gli implicanti primi hanno una forma molto omogenea tra loro. Un esempio di questo fenomeno e' la funzione dell'esempio 1, descritta nel paragrafo successivo, che, a fronte di 50 mintermini genera 90 implicanti primi, tutti composti da 4 variabili. Proprio questa omogeneita' negli implicanti primi genera un numero elevatissimo di tabelle cicliche da ridurre (piu' di 3 milioni per l'esempio 1). Sarebbe interessante studiare il legame tra forma degli implicanti primi e tabelle cicliche, ma questo argomento va al di la' dello scopo del nostro lavoro. Le funzioni piu' pesanti sono proprio quelle generate come la funzione dell'esempio 1, immesse cioe' tramite il meccanismo delle configurazioni di bit. Le funzioni migliori si hanno richiedendo range di configurazioni, e per l'esattezza i range centrali, come e' il caso dell'esempio 1. Utilizzando gli altri due meccanismi di immissione (Elenco o Casuale), le funzioni piu' significative vengono create scegliendo un numero non troppo elevato di mintermini, ma anche non troppo basso, distribuito uniformemente sull'arco delle configurazioni possibili. Sembra quindi che i risultati piu' importanti vengano raggiunti stando nel mezzo, adottando una giusta misura e LAAMEB 1.01 pag. 14 sensibilita' nella selezione dei mintermini. Da un punto di vista dell'algoritmo utilizzato, non si riscontrano prestazioni sostanzialmente differenti utilizzando lo stesso algoritmo nelle due direzioni ammesse. Cio' che cambia e' tipicamente l'elenco dei mintermini che compongono il minimo, e non il numero totale, facendo presupporre che in realta' esistano molti minimi diversi della stessa funzione. Il comportamento dei tre algoritmi e' invece molto diverso da caso a caso. Quine I esamina in modo esauriente l'albero delle scelte, ed e' quello fra i tre che ha i tempi di esecuzione piu' elevati, nonche' i parametri di minimizzazione (forme prime paragonate, tabelle cicliche esaminate) numericamente piu' grandi. Quine II presenta degli abbattimenti notevoli nelle dimensioni di questi parametri, in special modo nel numero di forme prime paragonate, ma non del tempo di elaborazione: questo si riduce di una frazione piccolissima, tanto da poter essere osservata solo su funzioni pesanti, come quella dell'esempio 1. Cio' e' dovuto principalmente al fatto che il tempo di elaborazione non dipende tanto dal numero di forme paragonate, quanto dalle tabelle ridotte, numero diminuito in maniera meno sensibile. Inoltre le funzioni di riduzione delle tabelle sono molto efficienti, e l'introduzione di un calcolo per il taglio di soluzioni svantaggiose aggiunge un tempo di elaborazione che e' solo leggermente inferiore a quello di riduzione tagliato. Fast Quine, invece, ha un tempo di elaborazione lineare, e non piu' esponenziale, in quanto non permette il fenomeno dell'esplosione combinatoria, a prezzo della qualita' della soluzione. Come si puo' notare nell'esempio 1, pero', a fronte di un'esecuzione di 3 secondi (Fast Quine dx), il programma fornisce una soluzione contenente 16 implicanti primi, contro i 15 del minimo (ottenuto pero' con un'elaborazione di piu' di 10 ore!). Logicamente non si ha nessuna garanzia sulla qualita' della soluzione fornita da questo algoritmo, anche se in generale si tratta di una buona approssimazione. 3.1 ALCUNI ESEMPI INTERESSANTI Gli esempi successivi sono stati ottenuti tutti mediante elaborazione con un algoritmo unico, cioe' senza interruzione, e con PR_CYCLE pari a 10000. Il computer utilizzato e' un PC desktop con microprocessore Intel 80486 DX 33 MHz, cache di 64 Kb, e RAM di 4 Mb (anche se attualmente vengono utilizzati solo i primi 640 Kb di memoria convenzionale). Prestazioni sensibilmente migliori potrebbero essere ottenute con un microprocessore Intel 80486 DX2 66 MHz o equivalenti, e aumentando fino a 256 Kb la cache on-board. Ogni esempio e' stato salvato su file mediante la funzione salva-testo. Per ogni esempio si hanno 6 file, corrispondenti alle 6 combinazioni di metodi e direzioni di minimizzazione. Ad ogni file e' stato poi aggiunto l'algoritmo utilizzato in fase B, in modo tale da renderne piu' efficiente la lettura. Esempio 1: 6 variabili, configurazioni da 2 a 4 uni - Quine I dx (es11.txt): tempo 10:06:31, forme 3449719, tabelle 3449718, 15 implicanti primi nella soluzione - Quine I sx (es12.txt): tempo 10:06:31, forme 3449719, tabelle 3449718, 15 implicanti primi nella soluzione - Quine II dx (es13.txt): tempo 10:03:19, forme 1418396, tabelle 3371359, 15 implicanti primi nella soluzione - Quine II sx (es14.txt): tempo 10:03:57, forme 1500353, tabelle 3376771, 15 implicanti primi nella soluzione - Fast Quine dx (es15.txt): tempo 00:00:03, forme 1, tabelle 29, 16 implicanti primi nella soluzione - Fast Quine sx (es16.txt): tempo 00:00:01, forme 1, tabelle 12, 18 implicanti primi nella soluzione Esempio 2: 8 variabili, elenco: 10-20,40-50,70-80,100-110,130-140,170-180, 200-210,230-240 - Quine I dx (es21.txt): tempo 00:00:02, forme 162, tabelle 161, 24 implicanti primi nella soluzione LAAMEB 1.01 pag. 15 - Quine I sx (es22.txt): tempo 00:00:01, forme 162, tabelle 161, 24 implicanti primi nella soluzione - Quine II dx (es23.txt): tempo 00:00:01, forme 75, tabelle 161, 24 implicanti primi nella soluzione - Quine II sx (es24.txt): tempo 00:00:01, forme 75, tabelle 161, 24 implicanti primi nella soluzione - Fast Quine dx (es25.txt): tempo 00:00:00, forme 1, tabelle 8, 24 implicanti primi nella soluzione - Fast Quine sx (es26.txt): tempo 00:00:00, forme 1, tabelle 4, 24 implicanti primi nella soluzione Esempio 3: 8 variabili, elenco: 10-20,40-50,70-80,100-110,130-140,160-170, 190-200,220-230 - Quine I dx (es31.txt): tempo 00:04:09, forme 14496, tabelle 14495, 23 implicanti primi nella soluzione - Quine I sx (es32.txt): tempo 00:04:08, forme 14496, tabelle 14495, 23 implicanti primi nella soluzione - Quine II dx (es33.txt): tempo 00:04:08, forme 10000, tabelle 14495, 23 implicanti primi nella soluzione - Quine II sx (es34.txt): tempo 00:04:08, forme 10012, tabelle 14495, 23 implicanti primi nella soluzione - Fast Quine dx (es35.txt): tempo 00:00:01, forme 1, tabelle 16, 23 implicanti primi nella soluzione - Fast Quine sx (es36.txt): tempo 00:00:01, forme 1, tabelle 9, 24 implicanti primi nella soluzione Esempio 4: 8 variabili, generazione casuale di 240 mintermini a partire dal seme 23 - Quine I dx (es41.txt): tempo 00:08:28, forme 27199, tabelle 27198, 21 implicanti primi nella soluzione - Quine I sx (es42.txt): tempo 00:08:28, forme 27199, tabelle 27198, 21 implicanti primi nella soluzione - Quine II dx (es43.txt): tempo 00:08:14, forme 1312, tabelle 22497, 21 implicanti primi nella soluzione - Quine II sx (es44.txt): tempo 00:08:16, forme 1881, tabelle 22922, 21 implicanti primi nella soluzione - Fast Quine dx (es45.txt): tempo 00:00:19, forme 1, tabelle 14, 23 implicanti primi nella soluzione - Fast Quine sx (es46.txt): tempo 00:00:19, forme 1, tabelle 10, 25 implicanti primi nella soluzione Esempio 5: 5 variabili, elenco: 10-30 - Quine I dx (es51.txt): tempo 00:00:00, forme 2, tabelle 1, 5 implicanti primi nella soluzione - Quine I sx (es52.txt): tempo 00:00:00, forme 2, tabelle 1, 5 implicanti primi nella soluzione - Quine II dx (es53.txt): tempo 00:00:00, forme 2, tabelle 1, 5 implicanti primi nella soluzione - Quine II sx (es54.txt): tempo 00:00:00, forme 2, tabelle 1, 5 implicanti primi nella soluzione - Fast Quine dx (es55.txt): tempo 00:00:00, forme 1, tabelle 1, 5 implicanti primi nella soluzione - Fast Quine sx (es56.txt): tempo 00:00:00, forme 1, tabelle 1, 5 implicanti primi nella soluzione 4 PROSPETTIVE LAAMEB non e' un programma chiuso, ma in quanto laboratorio si puo' intendere in continua evoluzione. Questo capitolo vuole gettare un veloce sguardo verso quello che puo' essere il futuro del prodotto, partendo da dove e' nato e valutandone le prospettive. LAAMEB 1.01 pag. 16 4.0 COME E' NATO LAAMEB Il programma e' nato come tesina per l'esame di Sistemi di Automazione 1, del II anno di corso della facolta' di Scienze dell'Informazione, di cui il prof. Torelli e' titolare. Fin dal primo momento, tutte le risorse degli autori sono state indirizzate verso l'ottimizzazione degli algoritmi implementati, perdendo un po' di vista l'aspetto riguardante l'interfaccia utente. Quest'ultima e' stata realizzata utilizzando delle finestre a carattere, senza mettere in atto meccanismi particolari di overlap o che velocizzassero l'accesso a video, come si puo' notare su macchine particolarmente lente. Questa prima release di LAAMEB vuole solo essere solo uno strumento valido, efficace e il piu' possibile veloce nel calcolo della minimizzazione. 4.1 COME POTRA' EVOLVERSI L'evoluzione di LAAMEB puo' avvenire su molte linee; cercheremo qui di riportare quelle principali individuate dagli autori: - miglioramento dell'interfaccia utente, con gestione automatica di mouse e overlapping windows - redirezione su stampante delle statistiche - arricchimento delle statistiche di minimizzazione, riportando ad es. la lista dei minimi incontrati e la tabella in corrispondenza della quale si ha avuto il minimo - funzione di salvataggio periodico nelle elaborazioni piu' pesanti - inserimento di euristiche nella ricerca del minimo, sia a livello dell'ordine di valutazione degli algoritmi esaustivi, sia a livello del taglio delle possibili soluzioni per algoritmi che non conducono al minimo - implementazione di particolari algoritmi per il calcolo degli implicanti primi, che permettano un taglio iniziale degli stessi, con conseguente abbattimento drastico delle tabelle cicliche da esaminare - allargamento delle minimizzazione a funzioni con piu' di 8 variabili - implementazione di algoritmi di minimizzazione che rendano minimo il numero di porte and, a parita' di porte or Chiunque fosse interessato a collaborare nella messa a punto di release future del pacchetto, o abbia dei quesiti particolari, e' pregato di rivolgersi, previa registrazione, a Giuliano Bossi, attraverso una delle modalita' riportate all'inizio di questa documentazione. 5 BIBLIOGRAFIA 1) LUCCIO F., PAGLI L., "Reti logiche e calcolatore", 1986, Bollati Boringhieri 2) SEDGEWICK R., "Algorithms in C", 1990, Addison-Wesley